package niuke.week02;

import java.util.HashSet;
import java.util.Scanner;

/**
 给定一个不含有1的正数数组arr，假设其中任意两个数为a和b，如果a和b的最大公约数 比1大，那么认为a和b之间有路相连;
 如果a和b的最大公约数是1，认为a和b之间没有路相连。
 那么arr中所有的数字就可以组成一张图，求arr中有多少个连通区域 2，求arr中的最大的连通区域中有多少个数。
 */
public class MaxUnion {

    static class UnionSet{
        private int []id;// id【i】表示i号数据所在的连通区域
        private int []count;// count【i】表示i号联通区域的元素个数
        private int n;

        UnionSet(int n ){
            this.n = n;
            id = new int[n];
            count = new int[n];
            for (int i = 0; i < id.length; i++) {
                id[i] = i;//每个人都属于不同的联通区域
                count[i] = 1; //每个连通区域的个数都为1
            }
        }

        public boolean isConnected(int p, int q) {
            return id[q]==id[p];//p和q所在的连通区与是不是同一个
        }

        public void unionElements(int p, int q) {
            int qId = id[q];//q的联通区域
            int pId = id[p];//p的连通区与
            if(qId==pId)
                return ;
            for(int i=0;i<id.length;i++)
                if(id[i]==qId){
                    id[i]=pId;//把q的联通区域换成p的连通区
                    count[pId]++;//PID增多了
                    count[qId]--;//QID减少了
                }
        }
        public int getUnionNunber(){
            int sum=0;
            for (int i = 0; i < n; i++) {
                if(count[i]!=0)
                    sum++;
            }
            return sum;
        }

        public int getMaxUnion(){
            int max=Integer.MIN_VALUE;
            for (int i = 0; i < n; i++) {
                max = Math.max(count[i],max);
            }
            return max;
        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int []arr = new int[n];
        for(int i = 0; i< n; i++)
            arr[i] = sc.nextInt();

        UnionSet unionSet = new UnionSet(n);

        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++)
                if(getMinYue(arr[i],arr[j]) >1)//i,j两个相连
                    unionSet.unionElements(i,j);
        }
        System.out.print(unionSet.getUnionNunber()+" "+unionSet.getMaxUnion());
    }


    public static int getMinYue(int a ,int b){
        int r = 1;
        do{
            r = a % b ;
            a = b;
            b = r;
            /*
            辗转相除法
            a对b取余，b赋值给a 余数赋值给b，，直到 b == 0
             */
        }while(b != 0);
        return a;
    }
}